enum Result {
    TRUE, FALSE
}

class RegularExpression {

    public static void main(String[] args) {
        System.out.println(RegularExpression.isMatch("aa", "a"));//false
        System.out.println(RegularExpression.isMatch("aaa", "aaaa"));//false
        System.out.println(RegularExpression.isMatch("mississippi", "mis*is*p*."));//false
        System.out.println("");
        System.out.println(RegularExpression.isMatch("aa", "a*"));///true
        System.out.println(RegularExpression.isMatch("ab", ".*"));//true
        System.out.println(RegularExpression.isMatch("aab", "c*a*b"));//true
        System.out.println(RegularExpression.isMatch("aaa", "a*a"));//true
        System.out.println(RegularExpression.isMatch("a", "ab*"));//true

        System.out.println("");

        System.out.println(RegularExpression.isMatch("aba", ".*b"));//false
        System.out.println(RegularExpression.isMatch("aba", ".*ab"));//false
        System.out.println(RegularExpression.isMatch("ab", ".*c"));//false
        System.out.println("");
        System.out.println(RegularExpression.isMatch("aba", ".*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*b.*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*ba"));//true
        System.out.println(RegularExpression.isMatch("abab", ".*ab"));//true
    }

    static Result[][] memo;

    public static boolean isMatch(String text, String pattern) {
        //使用一个二维数组去存储结果
        memo = new Result[text.length() + 1][pattern.length() + 1];
        return dp(0, 0, text, pattern);
    }

    public static boolean dp(int i, int j, String text, String pattern) {
        if (memo[i][j] != null) {
            //如果已经匹配过，就直接返回
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == pattern.length()) {
            //如果j结束了，i也结束了，那么当前结果是true
            ans = i == text.length();
        } else {
            //判断他们的第一个值是不是相等
            boolean first_match = (i < text.length() &&
                    (pattern.charAt(j) == text.charAt(i) ||
                            pattern.charAt(j) == '.'));

            //如果后一个是*，用回溯的思想
            if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                ans = (dp(i, j + 2, text, pattern) ||
                        first_match && dp(i + 1, j, text, pattern));
            } else {
                //否则向下走
                ans = first_match && dp(i + 1, j + 1, text, pattern);
            }
        }
        //记录当前的值
        memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        return ans;
    }
}
